package com.fr.lintcode;

public class Q1751 {

    /**
     * @param maze: the maze 
     * @return: Can they reunion?
     */
    public boolean findHer(String[] maze) {
        // Write your code here
    	int m = maze.length;
    	int n = maze[0].length();
    	boolean [][] traval = new boolean[m][n];
    	Point a = find(maze, 'S', m, n);
    	Point b = find(maze, 'T', m, n);
    	boolean success = false;
    	search(a, b, maze, success, traval, m, n);
    	return success;
    }
    

	private void search(Point a, Point b, String[] maze, boolean success, boolean[][] traval, int m, int n) {
		// TODO Auto-generated method stub
		if(success) {
			return;
		}else {
			if(a.x == b.x && a.y == b.y) {
				success = true;
				return;
			}
		}
		if(a.x + 1 < m && !traval[a.x + 1][a.y] && '.' == maze[a.x + 1].charAt(a.y)) {
			a.x = a.x+1;
			traval[a.x][a.y] = true;
			search(a, b, maze, success, traval, m, n);
			a.x = a.x-1;
		}
		if(a.y + 1 < m && !traval[a.x][a.y + 1] && '.' == maze[a.x].charAt(a.y + 1)) {
			a.y = a.y+1;
			traval[a.x][a.y] = true;
			search(a, b, maze, success, traval, m, n);
			a.y = a.y-1;
		}
		if(a.x - 1 >=0 && !traval[a.x - 1][a.y] && '.' == maze[a.x - 1].charAt(a.y)) {
			a.x = a.x-1;
			traval[a.x][a.y] = true;
			search(a, b, maze, success, traval, m, n);
			a.x = a.x+1;
		}
		if(a.y - 1 >0 && !traval[a.x][a.y - 1] && '.' == maze[a.x].charAt(a.y - 1)) {
			a.y = a.y-1;
			traval[a.x][a.y] = true;
			search(a, b, maze, success, traval, m, n);
			a.y = a.y-1;
		}
	}


	private Point find(String[] maze, char ch, int m, int n) {
		for(int i = 0 ; i < m; i ++) {
			String s = maze[i];
			for(int j = 0; j < n; j++) {
				char c = s.charAt(j);
				if(c == ch) {
					Point p = new Point();
					p.x = i;
					p.y = j;
				}
			}
		}
		return null;
	}


	class Point{
    	int x;
    	int y;
    }

}
